Объявление узлов
Объявление узла начинается с ключевого слова node, имени, необязательного выражения индексации и двоеточия. Выражение после двоеточия, описывающее состояние баланса в узле, может иметь любую из следующих форм:
net-expr = arith-expr net-expr <= arith-expr net-expr >= arith-expr arith-expr = net-expr arith-expr <= net-expr arith-expr >= net-expr arith-expr <= net-expr <= arith-expr arith-expr >= net-expr >= arith-expr
где arith-expr может быть любым арифметическим выражением, использующим ранее объявленные компоненты модели и определенные в настоящее время фиктивные индексы. Net-expr ограничен одним из следующих:
± net_in ± net_out ± net_in + arith-expr ± net_out + arith-expr arith-expr ± net_in arith-expr ± net_out
Каждый определенный таким образом узел вызывает ограничение в результирующей линейной программе. Имя узла обрабатывается как имя ограничения в командной среде AMPL, например, в операторе display.
Для объявлений, которые используют net_in, AMPL генерирует ограничение, подставляя его в том месте, где net_in появляется в условиях баланса. Объявления, использующие net_out, обрабатываются таким же образом. Выражения для входящего и исходящего потока выводятся из объявлений arc.
Объявление дуг
Объявление дуги состоит из ключевого слова arc, имени, необязательного индексного выражения и ряда необязательных уточняющих фраз. Каждая дуга создает переменную в результирующей линейной программе, значение которой представляет собой величину потока по дуге. Имя дуги может использоваться для ссылки на эту переменную в другом месте. Все фразы, которые могут появиться в определении var, имеют одинаковое значение в определении дуги. Чаще всего фразы >= и <= используются для определения значений для нижней и верхней границ потока вдоль дуги.
Фразы from и to определяют узлы, соединенные дугой. Направление потока обозначают словами from (от) и to(к). Именно эти интерпретации позволяют сделать вывод об ограничениях, связанных с узлами. Обычно в объявлении дуги указываются одно слово from или to, однако любое из них может быть опущено, как показано в модели выше:
arc Traff_In >= 0, to Intersection[entr];
arc Traff_Out >= 0, from Intersection[exit];
arc Traff {(i,j) in ROADS} >= 0, <= cap[i,j],
За любым из этих слов может следовать необязательное выражение индексации, которое должно соответствовать одному из двух типов:
- Выражение индексации, которое определяет - в зависимости от данных - пустой набор (в этом случае фраза from или to игнорируется) или набор с одним элементом (в этом случае используется фраза from или to).
- Индексирующее выражение специальной формы {if logic-expr}, которое заставляет использовать from или to тогда и только тогда, когда логическое выражение имеет значение true.
Можно указать, что дуга переносит поток из двух или более узлов, указывая более одного from или to фраз, или используя выражение индексации, которое определяет набор, имеющий более одного элемента. Однако результат этого, не является сетевой линейной программой, и AMPL отобразит соответствующее предупреждающее сообщение.
В конце фразы from или to можно добавить арифметическое выражение, представляющее коэффициент для умножения потока. Если коэффициент находится во фразе to, он умножает переменную arc при определении потока в указанном узеле. То есть, для заданного потока по дуге, величина, равная коэффициенту to, умноженному на поток, считается входящим в узел to. Коэффициент во фразе from интерпретируется аналогично. Коэффициент по умолчанию - 1.
Необязательная фраза obj определяет коэффициент, который умножит переменную дуги, чтобы создать линейный элемент в указанной целевой функции. Такая фраза состоит из ключевого слова obj, имени цели, которая ранее была определена в объявлении минимизации или максимизации, и арифметического выражения для значения коэффициента. За ключевым словом может следовать индексирующее выражение, которое интерпретируется как для from и to.
Взаимодействие с целевой функцией
Если все термины целевой функции указаны с помощью фраз obj в объявлениях arc, объявление цели происходит простым указанием minimize или maximize, за которым следует необязательное выражение индексации и имя. Это объявление должно стоять перед объявлениями arc, которые относятся к цели. В качестве альтернативы, имена дуг могут использоваться в качестве переменных для определения целевой функции обычным алгебраическим способом. В этом случае цель должна быть объявлена после дуг:
set INTER; # intersections
param entr symbolic in INTER; # entrance to road network
param exit symbolic in INTER, <> entr; # exit from road network
set ROADS within (INTER diff {exit}) cross (INTER diff {entr});
param cap {ROADS} >= 0; # capacities of roads
node Intersection {k in INTER};
arc Traff_In >= 0, to Intersection[entr];
arc Traff_Out >= 0, from Intersection[exit];
arc Traff {(i,j) in ROADS} >= 0, <= cap[i,j],
from Intersection[i], to Intersection[j];
maximize Entering_Traff: Traff_In;
Взаимодействие с ограничениями
Компоненты, определенные в объявлениях arc, могут использоваться как переменные в дополнительных объявлениях subject to. Последние представляют собой «боковые ограничения», которые налагаются в дополнение к балансу потока в узлах. В качестве примера рассмотрим, как можно построить задачу о потоках нескольких товаров, используя следующую формулировку сети узлов и дуг:
minimize Total_Cost;
set LINKS within (CITIES cross CITIES);
param supply {CITIES} >= 0; # amounts available at cities
param demand {CITIES} >= 0; # amounts required at cities
check: sum {i in CITIES} supply[i] = sum {j in CITIES} demand[j];
param cost {LINKS} >= 0; # shipment costs/1000 packages
param capacity {LINKS} >= 0; # max packages that can be shipped
minimize Total_Cost;
node Balance {k in CITIES}: net_in = demand[k] - supply[k];
arc Ship {(i,j) in LINKS} >= 0, <= capacity[i,j],
from Balance[i], to Balance[j], obj Total_Cost cost[i,j];
Мы вводим набор PRODS различных продуктов и добавляем его в индексное выражение всех параметров, узлов и дуг. Результатом является отдельная сетевая линейная программа для каждого продукта, целевая функция которой представляет собой сумму затрат для всех продуктов. Чтобы связать эти сети вместе, мы устанавливаем общий лимит на общие перевозки по любому звену:
param cap_joint {LINKS} >= 0;
subject to Multi {(i,j) in LINKS}:
sum {p in PRODS} Ship[p,i,j] <= cap_joint[i,j];
Результирующая модель не является сетевой линейной программой, но сетевая и несетевая ее части четко разделены:
set CITIES; set LINKS within (CITIES cross CITIES); set PRODS; param supply {CITIES,PRODS} >= 0; # amounts available at cities
param demand {CITIES,PRODS} >= 0; # amounts required at cities
check {p in PRODS}:
sum {i in CITIES} supply[i,p] = sum {j in CITIES} demand[j,p];
param cost {LINKS,PRODS} >= 0; # shipment costs/1000 packages
param capacity {LINKS,PRODS} >= 0; # max packages shipped
param cap_joint {LINKS} >= 0; # max total packages shipped/link
minimize Total_Cost;
node Balance {k in CITIES, p in PRODS}:
net_in = demand[k,p] - supply[k,p];
arc Ship {(i,j) in LINKS, p in PRODS} >= 0, <= capacity[i,j,p],
from Balance[i,p], to Balance[j,p], obj Total_Cost cost[i,j,p];
subject to Multi {(i,j) in LINKS}:
sum {p in PRODS} Ship[i,j,p] <= cap_joint[i,j];
Взаимодействие с переменными
Как переменная arc может использоваться в объявлении subject to, так и обычная переменная var может использоваться при объявлении node. То есть условие баланса в объявлении node может содержать ссылки на переменные, которые были определены в предыдущих объявлениях var. Эти ссылки определяют «побочные переменные» сетевой линейной программы. В качестве примера мы снова воспроизведем формулировку для набора PRODS.
minimize Total_Cost; Вся модель показана на рисунке 15-10.
set LINKS within (CITIES cross CITIES);
param supply {CITIES} >= 0; # amounts available at cities
param demand {CITIES} >= 0; # amounts required at cities
check: sum {i in CITIES} supply[i] = sum {j in CITIES} demand[j];
param cost {LINKS} >= 0; # shipment costs/1000 packages
param capacity {LINKS} >= 0; # max packages that can be shipped
minimize Total_Cost;
node Balance {k in CITIES}: net_in = demand[k] - supply[k];
arc Ship {(i,j) in LINKS} >= 0, <= capacity[i,j],
from Balance[i], to Balance[j], obj Total_Cost cost[i,j];
На этот раз мы свяжем сети вместе, введя набор исходных материалов и связанных данных:
set FEEDS; param yield {PRODS,FEEDS} >= 0;
param limit {FEEDS,CITIES} >= 0;
Мы предполагаем, что в городе k, помимо количества supply[p,k] продуктов, доступных для отгрузки, в продукты может быть преобразовано до limit[f,k] сырья f. Одна единица сырья f дает yield[p,f] единиц каждого продукта p. Переменная Feed[f,k] представляет количество сырья f, используемого в городе k:
var Feed {f in FEEDS, k in CITIES} >= 0, <= limit[f,k];
Условие баланса для продукта p в городе k теперь свидетельствует о том, что чистый отток равен чистому предложению плюс сумма количеств, полученных из различных видов сырья:
node Balance {p in PRODS, k in CITIES}: net_out = supply[p,k] - demand[p,k] + sum {f in FEEDS} yield[p,f] * Feed[f,k];
В заданном городе k переменные Feed[f,k] появляются в условиях баланса узлов для всех различных продуктов, объединяя продуктовые сети в единую линейную программу.
set CITIES; set LINKS within (CITIES cross CITIES); set PRODS; param supply {PRODS,CITIES} >= 0; # Предложение PRODS в каждом городе
param demand {PRODS,CITIES} >= 0; # Потребность PRODS в каждом городе
check {p in PRODS}:
sum {i in CITIES} supply[p,i] = sum {j in CITIES} demand[p,j];
param cost {PRODS,LINKS} >= 0; # стоимость транспартировки /1000 пакетов
param capacity {PRODS,LINKS} >= 0; # максимальное количество отправленных пакетов продукта
set FEEDS;
param yield {PRODS,FEEDS} >= 0; # количества, полученные из исходного сырья
param limit {FEEDS,CITIES} >= 0; # сырье доступное в городах
minimize Total_Cost;
var Feed {f in FEEDS, k in CITIES} >= 0, <= limit[f,k]; node Balance {p in PRODS, k in CITIES}: net_out = supply[p,k] - demand[p,k] + sum {f in FEEDS} yield[p,f] * Feed[f,k]; arc Ship {p in PRODS, (i,j) in LINKS} >= 0, <= capacity[p,i,j],
from Balance[p,i], to Balance[p,j],
obj Total_Cost cost[p,i,j];
